/** 二分查找掩码 */
export const enum BinarySearchMask {
  /** 默认，只进行完全匹配，有重复项时不保证返回次序 */
  default = 0,
  /** 完全匹配或者大于 */
  nearbyGreater = 1,
  /** 完全匹配或者小于 */
  nearbyLess = 2,
  /** 有重复项时，优先返回第一个 */
  duplicatePreferFirst = 4,
  /** 有重复项时，优先返回最后一个 */
  duplicatePreferLast = 8,
}
/**
 * 二分查找，返回在数组中查找到的元素
 * @param datas 有序的数组
 * @param compareFunc 比较函数，返回0表示相等，大于0表示偏大，小于0表示偏小
 * @param nearby 就近原则
 * @returns
 */
export function binarySearch<T>(
  datas: Array<T>,
  compareFunc: (data: T, index: number) => number,
  mask = BinarySearchMask.default
) {
  const idx = binarySearchIndex(datas, compareFunc, mask);
  if (idx >= 0) {
    return datas[idx];
  }
}

/**
 * 二分查找，返回在数组上的索引
 * @param datas 有序的数组
 * @param compareFunc 比较函数，返回0表示相等，大于0表示偏大，小于0表示偏小
 * @param nearby 就近原则
 * @returns
 */
export function binarySearchIndex<T>(
  datas: Readonly<Array<T>>,
  compareFunc: (data: T, index: number) => number,
  mask = BinarySearchMask.default
) {
  let left = 0;
  let right = datas.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const compareResult = compareFunc(datas[mid], mid);
    if (compareResult === 0) {
      // 完全匹配
      if (left === right) {
        return mid;
      }
      if (mask & BinarySearchMask.duplicatePreferFirst) {
        if (right === mid) {
          if (compareFunc(datas[left], left) === 0) {
            return left;
          }
          return right;
        }
        right = mid;
      } else if (mask & BinarySearchMask.duplicatePreferLast) {
        if (left === mid) {
          if (compareFunc(datas[right], right) === 0) {
            return right;
          }
          return left;
        }
        left = mid;
      } else {
        return mid;
      }
    } else if (compareResult > 0) {
      // 偏大
      right = mid - 1;
    } else {
      // 偏小
      left = mid + 1;
    }
  }
  if (mask & BinarySearchMask.nearbyGreater) {
    return left < datas.length ? left : -1;
  } else if (mask & BinarySearchMask.nearbyLess) {
    return right;
  }
  return -1;
}
